import java.util.Arrays;

public class Main {

    /**
     * 快速排序 Hoare版
     */
    /*public static void quickSort (int[] array) {
        quick(array, 0, array.length -1);
    }

    public static void quick(int[] array, int start, int end) {
        //为了预防数据是 1 2 3 4 5 6  要么没有左树，要么没有右树
        if (start >= end) {
            return;
        }
        //接收基准
        int pivot = partition(array, start, end);
        //递归掉方法
        quick(array, start, pivot - 1);
        quick(array, pivot + 1, end);
    }

    //查找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个数据
        int pivot = array[left];//将第一个数据给pivot
        while (left < right) {
            //要是<=、>=，而不是<、>
            while (left < right && array[right] >= pivot) {
                //右边找比pivot小的
                right--;//--说明没找到
            }
            while (left < right && array[left] <= pivot) {
                //左边找比pivot大的
                left++;//++说明没找到
            }
            //找到以后调用交换方法
            swap(array, left, right);//调用方法交换左边和右边的值
        }
        //此时已经遍历完成
        swap(array, left, i);//调用方法交换第一个元素和此时left的值
        return left;//返回的就是找到的基准
    }*/

    //交换的方法
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //快排练习
    /*public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);//调用方法开始分组
    }

    //分组治理的方法
    public static void quick(int[] array, int start, int end) {
        //预防没有左树或者没有右树
        if (start >= end) {
            return;
        }
        int ret = partition(array, start, end);//接受基准
        //调用方法递归查找基准
        quick(array, start, ret - 1);//左边小于的一组
        quick(array, ret + 1, end);//右边大于基准的一组
    }

    //找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个位置的值
        int pivot = array[left];//第一个元素给pivot
        //左边下标小于右边就进入循环
        while (left < right) {
            //r往左走找比pivot小的
            while (left < right && array[right] >= pivot) {
                //此时right向左边走 - 说明没找到
                right--;//右边先走
            }
            //l往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                //此时left往右走 - 说明没找到
                left++;
            }
            //此时找到了 - 交换l和r的值
            swap(array, left, right);
        }
        swap(array, left, i);//调用方法交换此时左边和i下标的值
        //此时基准查找完毕，返回这个基准
        return left;
    }*/

    //快排练习
    /*public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);//调用方法开始分组
    }

    //分组治理的方法
    public static void quick(int[] array, int start, int end) {
        //预防没有左树或者没有右树
        if (start >= end) {
            return;
        }
        int ret = partition(array, start, end);//接受基准
        //调用方法递归查找基准
        quick(array, start, ret - 1);//左边小于的一组
        quick(array, ret + 1, end);//右边大于基准的一组
    }

    //找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个位置的值
        int pivot = array[left];//第一个元素给pivot
        //左边下标小于右边就进入循环
        while (left < right) {
            //r往左走找比pivot小的
            while (left < right && array[right] >= pivot) {
                //此时right向左边走 - 说明没找到
                right--;//右边先走
            }
            //l往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                //此时left往右走 - 说明没找到
                left++;
            }
            //此时找到了 - 交换l和r的值
            swap(array, left, right);
        }
        swap(array, left, i);//调用方法交换此时左边和i下标的值
        //此时基准查找完毕，返回这个基准
        return left;
    }*/

    //快排练习
    /*public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);//调用方法开始分组
    }

    //分组治理的方法
    public static void quick(int[] array, int start, int end) {
        //预防没有左树或者没有右树
        if (start >= end) {
            return;
        }
        int ret = partition(array, start, end);//接受基准
        //调用方法递归查找基准
        quick(array, start, ret - 1);//左边小于的一组
        quick(array, ret + 1, end);//右边大于基准的一组
    }

    //找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个位置的值
        int pivot = array[left];//第一个元素给pivot
        //左边下标小于右边就进入循环
        while (left < right) {
            //r往左走找比pivot小的
            while (left < right && array[right] >= pivot) {
                //此时right向左边走 - 说明没找到
                right--;//右边先走
            }
            //l往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                //此时left往右走 - 说明没找到
                left++;
            }
            //此时找到了 - 交换l和r的值
            swap(array, left, right);
        }
        swap(array, left, i);//调用方法交换此时左边和i下标的值
        //此时基准查找完毕，返回这个基准
        return left;
    }*/

    //快排练习
    /*public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);//调用方法开始分组
    }

    //分组治理的方法
    public static void quick(int[] array, int start, int end) {
        //预防没有左树或者没有右树
        if (start >= end) {
            return;
        }
        int ret = partition(array, start, end);//接受基准
        //调用方法递归查找基准
        quick(array, start, ret - 1);//左边小于的一组
        quick(array, ret + 1, end);//右边大于基准的一组
    }

    //找基准的方法
    public static int partition(int[] array, int left, int right) {
        int i = left;//存储第一个位置的值
        int pivot = array[left];//第一个元素给pivot
        //左边下标小于右边就进入循环
        while (left < right) {
            //r往左走找比pivot小的
            while (left < right && array[right] >= pivot) {
                //此时right向左边走 - 说明没找到
                right--;//右边先走
            }
            //l往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                //此时left往右走 - 说明没找到
                left++;
            }
            //此时找到了 - 交换l和r的值
            swap(array, left, right);
        }
        swap(array, left, i);//调用方法交换此时左边和i下标的值
        //此时基准查找完毕，返回这个基准
        return left;
    }*/

    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    public static void quick(int[] array, int start, int end) {
        //预防只有左树或者只有右树
        if (start >= end) {
            return;
        }
        int ret = paririon(array, start, end);//接受基准
        //递归
        quick(array, 0, ret - 1);
        quick(array, ret + 1, end);
    }

    //找基准的方法
    public static int paririon(int[] array, int left, int right) {
        /*int i = left;//存储第一个位置的值
        int pivot = array[left];//第一个元素给pivot
        //左边下标小于右边就进入循环
        while (left < right) {
            //r往左走找比pivot小的
            while (left < right && array[right] >= pivot) {
                //此时right向左边走 - 说明没找到
                right--;//右边先走
            }
            //l往右走找比pivot大的
            while (left < right && array[left] <= pivot) {
                //此时left往右走 - 说明没找到
                left++;
            }
            //此时找到了 - 交换l和r的值
            swap(array, left, right);
        }
        swap(array, left, i);//调用方法交换此时左边和i下标的值
        //此时基准查找完毕，返回这个基准
        return left;*/
        int i = left;//存储left的值
        int p = array[left];
        while (left < right) {
            //r往左走找比p小的
            while (left < right && array[right] >= p) {
                //没找到 - 继续找
                right--;//往左走
            }
            //l往右走找比p大的
            while (left < right && array[left] <= p) {
                left++;//找下一个
            }
            //此时找到了交换left和right的值
            swap(array, left, right);
        }
        //交换left和i下标的值
        swap(array, left, i);
        return left;
    }

    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        quickSort(array);
        System.out.println("快排后：" + Arrays.toString(array));
    }
}
